#include <bf/bloom_filter/basic.hpp>

#include <cassert>
#include <cmath>

/*
1. 什么是 partition?
假设m = 20, k = 3, 存放数字num = 100， a, b, c为置为的位置
若partition = flase
a = hash1(num) % m, b = hash2(num) % m, c = hash3(num) % m
若partition = true
m = m + k - m % 20 = 20 + 3 - 2 = 21, 3个hash函数，每个分到7个bit位置
hash1的位置为0~6; hash2为7 ~ 13... ...
所以a = 7 * 0 + hash1(num) % 7; b = 7 * 1 + hash1(num) % 7 ... ...
*/

namespace bf {

size_t basic_bloom_filter::m(double fp, size_t capacity)
{
    auto ln2 = std::log(2);
    return std::ceil(-(capacity * std::log(fp) / ln2 / ln2));
}

size_t basic_bloom_filter::k(size_t cells, size_t capacity)
{
    auto frac = static_cast<double>(cells) / static_cast<double>(capacity);
    return std::ceil(frac * std::log(2));
}

basic_bloom_filter::basic_bloom_filter(hasher h, size_t cells, bool partition)
    : hasher_(std::move(h)), bits_(cells), partition_(partition)
{
}

basic_bloom_filter::basic_bloom_filter(double fp, size_t capacity, size_t seed,
                                       bool double_hashing, bool partition)
    : partition_(partition)
{   // 需要的位数
    auto required_cells = m(fp, capacity);
    // 需要的哈希函数的个数
    auto optimal_k = k(required_cells, capacity);
    // 使每个hash函数分到的bit数目一致，每个hash函数按顺序分配相同的bit数目
    if (partition_)
        required_cells += optimal_k - required_cells % optimal_k;
    bits_.resize(required_cells);
    hasher_ = make_hasher(optimal_k, seed, double_hashing);
}

basic_bloom_filter::basic_bloom_filter(hasher h, bitvector b)
    : hasher_(std::move(h)), bits_(std::move(b))
{
}

basic_bloom_filter::basic_bloom_filter(basic_bloom_filter&& other)
    : hasher_(std::move(other.hasher_)), bits_(std::move(other.bits_))
{
}

/*
 *  向bitvector中添加元素o
 */
void basic_bloom_filter::add(object const& o)
{
    // 通过hash函数计算k个位置
    auto digests = hasher_(o);
    if (partition_)
    {
        assert(bits_.size() % digests.size() == 0);
        auto parts = bits_.size() / digests.size();
        for (size_t i = 0; i < digests.size(); ++i)
            bits_.set(i * parts + (digests[i] % parts));
    }
    else
    {
        for (auto d : digests)
            bits_.set(d % bits_.size());
    }
}

size_t basic_bloom_filter::lookup(object const& o) const
{
    auto digests = hasher_(o);
    if (partition_)
    {
        assert(bits_.size() % digests.size() == 0);
        auto parts = bits_.size() / digests.size();
        for (size_t i = 0; i < digests.size(); ++i)
            if (!bits_[i * parts + (digests[i] % parts)])
                return 0;
    }
    else
    {
        for (auto d : digests)
            if (!bits_[d % bits_.size()])
                return 0;
    }

    return 1;
}

void basic_bloom_filter::clear()
{
    bits_.reset();
}

void basic_bloom_filter::remove(object const& o)
{
    for (auto d : hasher_(o))
        bits_.reset(d % bits_.size());
}

void basic_bloom_filter::swap(basic_bloom_filter& other)
{
    using std::swap;
    swap(hasher_, other.hasher_);
    swap(bits_, other.bits_);
}

bitvector const& basic_bloom_filter::storage() const
{
    return bits_;
}
hasher const& basic_bloom_filter::hasher_function() const
{
    return hasher_;
}

} // namespace bf
